package day01;

import java.util.Iterator;

/**
 * @author Jetwang
 * @version 1.0
 * @since 2023/3/18 16:36
 * 大顶堆实现(完全二叉树)
 */

@SuppressWarnings("all")
public class PriorityQueue03<E extends Priority> implements Queue<E>, Iterable<E> {
    Priority[] array;
    int size;

    public PriorityQueue03(int capacity) {
        array = new Priority[capacity];
    }

    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }
        int child = size++;
        int parent = (child - 1) / 2;
        while(child > 0 && e.priority() > array[parent].priority()) {
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] = e;
        return true;
    }


    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        swap(0, size - 1);
        size--;
        Priority e = array[size];
        array[size] = null; // help GC

        // 完成下潜
        down(0);
        return (E) e;
    }

    private void swap(int i, int j) {
        Priority temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    private void down(int parent) {
        int left = 2 * parent + 1;
        int right = left + 1;
        // 假设父元素优先级最大
        int max = parent;
        if (left < size && array[left].priority() > array[max].priority()) {
            max = left;
        }
        if (right < size && array[right].priority() > array[max].priority()) {
            max = right;
        }
        if (max != parent) {
            swap(max, parent);
            // 继续下潜 递归调用
            down(max);
        }
    }


    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return array.length == size;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int i = 0;
            @Override
            public boolean hasNext() {
                return i < size;
            }

            @Override
            public E next() {
                E val = (E) array[i];
                i++;
                return val;
            }
        };
    }
}
